import collections
from typing import List


class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = collections.defaultdict(set)
        for edge in connections:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])

        ans = []

        dfn = [-1] * n
        low = [-1] * n

        def dfs(last, now, depth):
            dfn[now] = depth
            low[now] = depth
            for nxt in graph[now]:
                if nxt == last:
                    continue
                if dfn[nxt] == -1:
                    dfs(now, nxt, depth + 1)
                    if dfn[now] < low[nxt]:
                        ans.append([now, nxt])
                low[now] = min(low[now], low[nxt])

        dfs(-1, 0, 1)

        return ans


if __name__ == "__main__":
    # [[1,3]]
    print(Solution().criticalConnections(n=4, connections=[[0, 1], [1, 2], [2, 0], [1, 3]]))
